package gold.digger;

import javafx.util.Pair;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC394 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public String decodeString(String s) {
            return getStrRecur(s, 0, s.length() - 1).getKey();
        }

        public Pair<String, Integer> getStrRecur(String s, int begin, int end) {
            if (begin > end) return new Pair<>("", end);

            StringBuilder res = new StringBuilder();
            int i = begin;
            while (i <= end) {
                if ('[' == s.charAt(i)) {
                    ++i;
                    continue;
                }

                if (']' == s.charAt(i)) {
                    //结束当前子递归
                    return new Pair<>(res.toString(), i + 1);
                }

                if (Character.isDigit(s.charAt(i))) {
                    //当前位是数字，需要递归执行
                    int j = i + 1;
                    while (j <= end && Character.isDigit(s.charAt(j))) ++j;
                    int count = Integer.parseInt(s.substring(i, j));
                    Pair<String, Integer> subRes = getStrRecur(s, j + 1, end);
                    for (int k = 0; k < count; k++) {
                        res.append(subRes.getKey());
                    }
                    i = subRes.getValue();
                    continue;
                } else {
                    res.append(s.charAt(i++));
                }
            }

            return new Pair<>(res.toString(), end);
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.decodeString("abc3[cd]xyz"));
    }

    public static void main(String[] args) throws Exception {
        LC394 an = new LC394();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
